1. Field of the Invention
The present invention relates in general to a system for storing and retrieving data in database records referenced by binary number keys having a few randomly-placed, non-deterministic bits.
2. Description of Related Art
U.S. Pat. No. 6,161,213 issued Dec. 12, 2000 to Lofstrom (incorporated herein by reference) describes an identification (ID) generation circuit embedded in an integrated circuit (IC) chip for generating a binary bit pattern that can serve as a chip ID. The ID generation circuit makes use of randomly occurring parametric variations inherent in the integrated IC manufacturing process when generating the ID in a way that ensures that the ID is highly likely to be unique for each IC chip in which the ID generation circuit is embedded, even though the same set of masks are used when fabricating the ID generation circuit in a large number of ICs. The ID generation circuit, which can be employed for example in any standard sub-micron CMOS process, does not require technologies such as EPROMs, flash memories, or poly fuses, or post fabrication techniques such as laser-trimmed fuses or links. These alternatives typically require more complex manufacturing process steps. Furthermore, each individual IC chip must be separately processed after manufacturing in order to load a unique ID into each IC chip. Since the embedded IC generation circuit requires no additional manufacturing process steps or expensive machinery to separately program each IC chip, the chip ID system it provides is less expensive to implement than other approaches.
The embedded ID generation circuit produces its output ID pattern based on the binary outputs of an array of ID cells, wherein each cell output is a function of random process variations in doping of transistor channels within the cell. Due to the analog nature of the transistor operating characteristic each cell measures when determining the state to which it sets its output bit, and due to such other effects as thermal and system noise, among the ID bits produced by the chip""s ID circuit cells, a very small percentage of the bits of the chip ID may be xe2x80x9cnon-deterministicxe2x80x9d in the sense that the cells do not always set their output bits to the same value each time they generate them. Thus sometimes a particular bit of an ID read out of an IC chip will be set to a xe2x80x9c0xe2x80x9d, while other times the bit will be set to a xe2x80x9c1xe2x80x9d. The bit locations within a cell""s ID where such bit xe2x80x9cdriftingxe2x80x9d might occur are randomly distributed across the IDs for a large collection of ICs. However while a few of the bits of any particular IC chip""s ID may drift in this manner, if the ID is sufficiently large, the great majority of the bits of the ID are xe2x80x9cdeterministicxe2x80x9d in that they will always have the same value whenever the ID generation circuit generates the chip""s ID.
Thus by making the number of bits in the ID sufficiently large, the ID for any one IC chip can be statistically guaranteed, with a high degree of certainty, to be uniquely distinct from IDs generated by millions of other IC chips, even though all of the chips employ the same ID circuit to generate their IDs, and even though some of the bits of many of the IDs may drift.
Lofstrom teaches that given a population of previously retrieved non-deterministic IDs such as would be generated by ID generation circuits embedded in a large collection of IC chips, and given an incoming ID newly acquired from one IC, the new ID can be compared with the previously retrieved IDs to determine whether the new ID came from one of the collection of IC chips. Lofstrom further teaches that, if so, the identity of the IC chip from which the incoming ID can be determined even in the presence of bit drifting. One example technique for comparing ID bit patterns involves computing an absolute norm (also called the xe2x80x9cHamming Distancexe2x80x9d, or xe2x80x9cHDxe2x80x9d) between the two ID bit patterns. The HD of any two bit patterns is simply the number of bit positions where the two ID patterns differ. In accordance with the technique, the HD between two chip ID bit patterns are compared with a predefined HD threshold HDth, and when the HD is less than HDth, then the two chip IDs must have come from the same IC, otherwise, they must have come from two separate ICs. This technique shall be referred to herein as the xe2x80x9cHD-Matchingxe2x80x9d technique, and when two chip IDs have an HD less than HDth, they are considered to exhibit an xe2x80x9cHD-Matchxe2x80x9d, as the term is used herein below.
An ID key produced by the embedded ID generation circuit may consist of two fields: a xe2x80x9ctypeIDxe2x80x9d field in which all bits are programmed at the mask level so that they are the same for all IC chips of the same type, and a xe2x80x9cuniqueIDxe2x80x9d field that is generated by the aforementioned cells and which is unique for each chip. The appropriate bit width of the uniqueID field of the chip ID needed to ensure that all chips of the same type will have unique IDs depends largely on the number of chips of that type to be produced and the number of bits that can be expected to be non-deterministic.
An array of IC dice are typically manufactured on a wafer and then separated to form individual IC chips. However integrated circuit manufacturers test and make measurements on various operating parameters of the ICs while they are still in wafer form by using probes to access input/output pads on the surfaces of the die. When an IC tester tests ICs having the embedded ID generation circuits, it can also read out their IDs and store them in a database containing other information about the ICs. The ID read out of each die can serve as the unique, permanent identification for that particular die, throughout its life from xe2x80x9cbirth to deathxe2x80x9d, as the die passes through the various wafer-level measurement, testing, and burn-in processing steps, chip-level packaging and final testing, shipment to distributors and end-users, and assembly and use in an end-system, until the chip fails or is discarded.
It would be helpful to provide a database in which information about each chip could be stored in one or more databases, in records keyed to the chip""s ID, so that the information could be retrieved when needed. However the difficulty in using a conventional database to store and retrieve information about the chip, is that some of the chips"" ID""s can have a few non-deterministic bits in randomly distributed bit locations. A conventional database system can only store a record using a key of a particular (fixed) value, and it can only retrieve that record if it is queried with a key having exactly the same value as the key under which the record was stored. Due to the non-deterministic nature of one or more bits of the ID read out of some of the IC chips, an ID newly read out of an IC chip may not exactly match any of the IDs previously read out of that same chip and supplied to the database when the database stored the information in the database. Thus using the ID read out of the chip as a key, a conventional database requiring deterministic ID keys will not be able to locate all of the records relating to a particular IC.
Even if a conventional database is retrofitted to deal with non-deterministic keys due to bit drifting, for example, by conducting the aforementioned HD-matching operation while trying to determine a key match, it still faces an efficiency problem. Conventional databases use such techniques as indexing, hashing, and the various sorting/searching schemes using the record keys to store and locate data records. But when presented with a new, potentially drifting key, all the indexing, hashing, and search techniques will break down. One way to resolve the problem is to create a record for each IC chip using the ID it generated when the record was first created as a key to the storage location of the record in the database. The keys to records for all chips are stored in a list. Thereafter, whenever it is necessary to read or write access the IC""s record, the chip ID is read out of the IC and compared to each successive chip ID on the list until an HD-matching chip ID is found. The difficulty with such an approach is that it requires the database system to compare the chip""s newly output ID to, on average, one half of the chip IDs in the database. This can be very time-consuming when the database includes records for a large number of IC chips. What is needed is a database system that can make use of a binary number having a few randomly-positioned, non-deterministic bits as a key for identifying records, and yet be able to quickly determine which record each key references.
A database system in accordance with the invention read and write accesses database records referenced by a binary number key (such as the aforementioned chip ID) having two fields, a typeID field containing only deterministic bits, and a uniqueID field permissibly containing one or more non-deterministic bits at any bit positions therein. The database system maintains a set of databases, each being identified by a separate value of the typeID field of the binary number key. The records of each database are allocated among a plurality of bins, with each bin being identified (keyed) by separate value of a binID field, and with each record being identified (keyed) by a separate value of a recID field.
The database system locates a record of interest referenced by the binary number key by first selecting a particular one of the databases that is identified by the typeID field of the binary number key. It then compares a portion of selected bits of the binary number key""s uniqueID field to binID values identifying bins of the selected database to determine a subset of the bins that may include the record of interest.
The database system then compares the full uniqueID field of the binary number key to the recIDs values for records of the subset of bins to determine which particular recID field identifies the record of interest. The claims appended to this specification particularly point out and distinctly claim the subject matter of the invention. However those skilled in the art will best understand both the organization and method of operation of what the applicant(s) consider to be the best mode(s) of practicing the invention, together with further advantages and objects of the invention, by reading the remaining portions of the specification in view of the accompanying drawing(s) wherein like reference characters refer to like elements.